This invention relates to cryptographic techniques, and more particularly to digital signatures.
For centuries, people have been searching for ingenious methods to communicate privately and secretly. The methods can simply be substituting one letter for another as Julius Caesar did, or as complicated as the mechanical "Enigma" system used by the Germans during W.W.II, which took hundreds of researchers years to crack.
Many secret communication methods depend on some secret information, also known as a "secret code," agreed upon between the sender and the receiver. The sender is also known as the sender token, and the receiver is also known as the receiver token; each token can be a computer, a person or even just an intelligent bank card. The complexity of the problem significantly increases when the sender and the receiver have never met before, such as a buyer trying to pay for a coat bought from a seller through the Internet by giving the seller his or her charge card number. If they have not met before, they cannot securely settle on a secret code to communicate among themselves. The secret code has to be set through some initial communication. Unfortunately, the initial communication can be eavesdropped, with the secret code exposed.
The public-private key encryption technique has resolved the above-identified problem. Based on a public-key/private-key key pair, every digital message can be encrypted by any one of the key and decrypted by the other, with the public keys recorded in a public directory, which is publicly accessible, and the private key privately retained. Typically, the sender of the message would go to the public-key directory to look for the receiver's public key. Then the sender would encrypt the message with the receiver's public key, and convey the encrypted message to the receiver. The receiver, upon getting the encrypted message, decrypts the message with her private key. Such a public-private key scheme resolves the problem of maintaining the secrecy of a communication. However, when the receiver gets the message, the receiver cannot be certain that the message is from the sender. The receiver would like to have the equivalence of a signature on the message.
The public-private key encryption technique can also be used to generate a digital signature to authenticate the sender. Typically, the sender would hash the message with a one-way hashing function that is publicly known and is an agreed-upon standard, such as published in the newspaper. Hashing a message is a computation applied to a message that collapses the message and transforms it to a unique value--no two messages have the same value. After hashing, the sender would digitally sign the message by encrypting the hashed message with her private key. Both the digital signature and the message will be encrypted by the receiver's public key, and are then sent to the receiver. The receiver, upon getting the information, decrypts it, and extracts the digital signature from it. Then the receiver gets the sender's public key from the public directory to decrypt the digital signature to get back the same message. This operation ensures the identity of the sender because she is the only person who can encrypt the message with her private key. One cryptosystem that allows digital signatures with message-recovery is RSA. There are also ElGamal variants, which allow signing with message recovery.
Basic concepts on public-key encryption, digital signatures, and one-way hash functions are well known to those with ordinary skill in the art of cryptography. Details can be found in many textbooks, including Applied Cryptography, 2nd Edition, by Bruce Schneier (John Wiley & Sons, 1996).
The above described operations or protocols are secure as long as the encryption scheme is not broken. One way to break a protocol is to reverse-engineer the physical system that executes the protocol, and to then modify the protocol. One solution to this problem is to execute the protocol in a tamper-resistant hardware device. There are many techniques for making hardware device (such as a portable computer or a token) tamper-resistant, and they are well known in the current art. Examples of tamper-resistant hardware include PC-MCIA cards from National Semiconductor, Inc. and Datakey, button-memory devices from Dallas Semiconductor, Inc., and authenticator tokens by Security Dynamics, Inc. The U.S. government uses tamper-resistant hardware for many of its military encryption and decryption equipment.
Another way to break the protocol is to break the public-private key encryption one of the cryptographic algorithms (the public key algorithm, the hash function, the bulk encryption algorithm, etc.), which can be an almost impossible task. A public-key key-size of more than 512 bits would require over ten thousand MIP years to break with conventional computational methods and equipment.
However, if one is not careful, his protocols can still be broken. For example, in 1995, two researchers broke Netscape's protocol. They did not break the public-private key encryption, but they broke the key-generation procedure. In Netscape's protocol, two users, after they have secured communication through exchanging their keys, would transmit to each other a "secret code" or a session key based on their secured communication channel. From that point onwards, their communication will be encrypted using the session key, because an encryption using a session key needs much less time than an encryption method based on the public-private key set. Typically, a session key is based on a long random number. In Netscape case, a part of the session key is based on predictable numbers, such as the serial number of one of the user's computer. The two researchers somehow figured out the predictable part of the session key, broke it and exposed the secured communication between the users.
No matter how strong a protocol is, there might be a possibility that it can be broken, reverse-engineered, or it can be stolen. A user, after being aware that her protocol has been broken, should be protected from the attacker or the intruder changing the protocol and convincing her to use the old, broken protocol as if it were a new protocol. There has to be some auditing trail established so that she could trace back all the transactions by the hardware device (or software program) token to ensure her that what she has is a new protocol. This auditing trail can be based on the version of the protocol, the ID number of the hardware device (or software program)token and the ID number of the public-private key set. But, no matter what the trail is based on, there should be some way to ensure the user the security of her token.
Similarly, the user might encounter the same problem if she has lost her hardware device token or if her hardware device token has been stolen. There must be some way to protect her so that unauthorized use could only last for a short duration of time, and all the unauthorized use can be traced back so that she is not liable for any of those transactions. Again, one needs to have an audit trail created to trace the sequence of events or transactions using the hardware device token. This would help the user to recover after losing her hardware device token or after her hardware device token was broken into.
There are also many applications with a need for strong audit trail. The most obvious applications with such needs are for key certification and key escrow agencies. In both cases, operations such as certifying public keys, recovering private or secret keys should not be performed without leaving an audit trail.
Another application with a need for auditing is electronic commerce. There are many financial interactions that would benefit from a strong audit trail: smart-card credit or debit cards interacting with an Automatic Teller Machine or a point-of-sale credit-card validation machine, Internet-based purchasing software interacting with commercial Websites, consumers interacting with Internet-based gambling services, etc. In all of these circumstances there is the need to establish an audit trail of actions between the various parties, so that an arbitrator (a judge, regulatory agency, etc.) can reconstruct events after they occurred.
One way to establish such an auditing trail is to use a portion of the message bits as a storage of all prior transactions of the hardware device (or software program)token. The prior transaction bits after they are hashed are sent out as a part of the message bits, and are stored by the recipient of the message. Such a process would create an audit trail because by unhashing the chain, one can trace back what has happened. Even if the hardware device token is broken, or the secure software process is reverse-engineered and modified, the attacker cannot change whatever that has been sent to the recipients in the past. The problem with this approach is that it wastes valuable space that could have been used for the message.
It should be apparent from the foregoing that there is still a need for an encryption scheme that has a strong audit trail while not wasting a lot of the valuable message space.